package com.peng.leetcode.dfs;

/**
 * CalculateMinimumHP
 * 174. 地下城游戏
 * <p>
 * 一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
 * <p>
 * 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
 * <p>
 * 有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
 * <p>
 * 为了尽快到达公主，骑士决定每次只向右或向下移动一步。
 * <p>
 * 链接：https://leetcode-cn.com/problems/dungeon-game
 *
 * @author: lupeng6
 * @create: 2021/1/19 17:15
 */
public class CalculateMinimumHP {

    public static void main(String[] args) {
//        int[][] dungeon = {{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}};
//        int[][] dungeon = {{3, 0, -3}, {-3, -2, -2}, {3, 1, -3}};
//        int[][] dungeon = {{3, -20, 30}, {-3, 4, 0}};
//        int[][] dungeon = {{1, -3, 2}, {0, -1, 2}, {0, 0, -2}};
        int[][] dungeon = {{0, 0, 0}, {-1, 0, 0}, {2, 0, -2}};
//        int[][] dungeon = {{0, -5}, {0, 0}};
        System.out.println(new CalculateMinimumHP().calculateMinimumHP(dungeon));
    }


    /**
     * 广度优先遍历
     *
     * @author lupeng6
     * @date 2021/1/19 17:16
     */
    public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon.length == 0) {
            return 0;
        }
        this.rows = dungeon.length;
        this.cols = dungeon[0].length;
        this.visited = new int[rows][cols];
        this.dungeon = dungeon;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                visited[i][j] = -1;
            }
        }
        int min = dfs(0, 0);
        return min;
    }

    public int dfs(int x, int y) {
        if (x == rows - 1 && y == cols - 1) {
            int step = dungeon[x][y];
            return step > 0 ? 1 : 1 - step;
        }
        if (visited[x][y] > 0) {
            return visited[x][y];
        }
        Integer goDown = Integer.MAX_VALUE;
        Integer goRight = Integer.MAX_VALUE;
        if (x < rows - 1) {
            goDown = dfs(x + 1, y);
        }
        if (y < cols - 1) {
            goRight = dfs(x, y + 1);
        }
        int currConsume;
        if (goDown < goRight) {
            currConsume = goDown - dungeon[x][y];
        } else {
            currConsume = goRight - dungeon[x][y];
        }

        if (currConsume <= 0) {
            visited[x][y] = 1;
        } else {
            visited[x][y] = currConsume;
        }
        return visited[x][y];
    }


    private int rows;

    private int cols;

    private int[][] visited;

    int[][] dungeon;

}
